package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.Stack;

/**
 * @Author: tgy @Date: 1/18/21 3:11
 *
 * 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。
 * 除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序?
 *
 * 其实是插入排序
 */
public class _05_使用一个栈实现另外一个栈的排序 {

    public static void sortStack(Stack<Integer> stack) {

        Stack<Integer> help = new Stack<>();

        while (!stack.isEmpty()) {

            int top = stack.pop();

            if (help.isEmpty() || help.peek()>= top) {

                help.push(top);
            }else {

                while (!help.isEmpty() && (help.peek() < top)) {

                    stack.push(help.pop());
                }

                help.push(top);
            }
        }

        while (!help.isEmpty()) {

            stack.push(help.pop());
        }
    }

    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<>();

        int[] nums = {4,2,5,1,3};

        for (int i = nums.length - 1; i >= 0; i--) {

            stack.push(nums[i]);
        }

        sortStack(stack);

        while (!stack.isEmpty()) {

            System.out.println(stack.pop());
        }
     }
}
